This is a phase I study of 5 Aza-2'-Deoxycytidine (DAC), a cytidine analog with activity as a demthylating agent in mammalian cells. Eligible patients will have incurable stages II or IV melanoma or other cancer with a least two surgically resectable or biopsiable lesions. The study is designed to define the optimal biologic dose of DAC, and evaluate the tocicity of DAC administered by twice daily extended intravenous infusions to cohorts of three to six patients with escalating doses. The primary biologic end points to be determined in this study are increases in levels of p16 expression as well as methylation changes in exon 1 of p16 in tumors. CDK4 and CDK6 cyclin levels will be measured. Expression of tumor antigen genes MAGE-1, -2 and -3, class I MHC, ICAM-1 (CD54) and LFA-1 (CD11b) will be assessed on biopsy specimens. Regression of tumor will be a clinical end point.